package diff;

import java.util.List;

class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

public class Diff {


    public int sumNumbers(TreeNode root) {
        return dfs(root,0);
    }

    private int dfs(TreeNode root, int presum) {

        presum = presum*10+root.val;
        if (root.left == null && root.right == null){
            return presum;
        }
        int ret = 0;
        if (root.left!=null)
            ret += dfs(root.left, presum);
        if (root.right != null){
            ret += dfs(root.right,presum);
        }
        return ret;
    }




    /*
    public boolean evaluateTree(TreeNode root) {
        if (root.left == null){
            return root.val == 0? false:true;
        }
        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        return root.val==2? left||right : left&&right;

    }


*/


//    public double myPow(double x, int n) {
//        return n<0?1.0/pow(x,-n):pow(x,n);
//    }
//
//    public double pow(double x, int n) {
//        if (n == 0){
//            return 1.0;
//        }
//        double tmp = pow(x,n/2);
//        return n%2==0 ? tmp*tmp:tmp*tmp*x;
//    }








    /*
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode temp = swapPairs(head.next.next);
        ListNode ret = head.next;
        ret.next = head;
        head.next = temp;
        return ret;


    }


*/









    /*
    public ListNode reverseList(ListNode head) {

        if (head == null || head.next==null){
            return head;
        }
        ListNode ret = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return ret;
    }

*/




/*
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }

        ListNode tmp = swapPairs(head.next.next);
        ListNode ret = head.next;
        ret.next = head;
        head.next = tmp;

        return ret;
    }
*/

    /*
    public ListNode reverseList(ListNode head) {
        if (head==null || head.next == null){
            return head;
        }

        ListNode newHead = reverseList(head.next);

        head.next.next = head;
        head.next = null;

        return newHead;
    }

     */


/*
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1==null)return list2;
        if (list2==null)return list1;

        if (list1.val <= list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else {
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }

    }

    private ListNode dfs(ListNode l1, ListNode l2) {

        if (l1==null){
            return l2;
        }
        if (l2==null){
            return l1;
        }

        if (l1.val < l2.val){
            l1.next = dfs(l1.next,l2);
            return l1;
        }else {
            l2.next = dfs(l1,l2.next);
            return l2;
        }






    }

*/


/*
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        diff(A,B,C,A.size());
    }

    private void diff(List<Integer> A, List<Integer> B, List<Integer> C, int n) {
        if (n==1){
            C.add(A.remove(A.size()-1));
            return;
        }

        diff(A,C,B,n-1);
        C.add(A.remove(A.size()-1));

        diff(B, A, C, n-1);

    }

*/
}
